﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
using namespace std;

#include <stack>
#include <vector>

struct TreeNode 
{
	int val;
	TreeNode* left;
	TreeNode* right;

	TreeNode() : val(0), left(nullptr), right(nullptr) {}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
	TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class Solution {
public:
	vector<int> postorderTraversal(TreeNode* root) {
		TreeNode* cur = root;
		stack<TreeNode*> s;
		vector<int> v;
		TreeNode* prev = nullptr;

		while (cur || !s.empty())
		{
			// 1、访问⼀颗树的开始
			while (cur)
			{
				s.push(cur);
				cur = cur->left;
			}

			TreeNode* top = s.top();
			// top结点的右为空 或者 上⼀个访问结点等于他的右孩⼦
			// 那么说明(空)不⽤访问 或者 (不为空)右⼦树已经访问过了
			// 那么说明当前结点左右⼦树都访问过了，可以访问当前结点了

			if (top->right == nullptr || top->right == prev)
			{
				s.pop();
				v.push_back(top->val);
				prev = top;
			}
			else
			{
				// 右⼦树不为空，且没有访问，循环⼦问题⽅式右⼦树
				cur = top->right;
			}
		}

		return v;
	}
};

int main()
{
	// root = [1,null,2,3]

	TreeNode* root = new TreeNode(1);
	
	root->right = new TreeNode(2);

	root->right->left = new TreeNode(3);

	auto v = Solution().postorderTraversal(root);

	for (const auto& num : v) cout << num << " ";
	cout << endl;

	return 0;
}
